The invention relates to an authentication method and a communication system for authentication.
Identification is performed in the field of transponder technology, and in particular in the field of contactless communication. Although in principle usable in any desired communication systems, the problem area underlying it is explained in what follows by reference to so-called RFID communication systems and their applications. Here, RFID stands for “Radio Frequency Identification”. As a general background to this RFID technology, refer to the “RFID-Handbuch” [RFID Manual] by Klaus Finkenzeller, Hansa-Verlag, third updated edition, 2002.
With the RFID systems known nowadays, the passive transponder (or tag) typically accepts an electromagnetic signal emitted by a base station (or read station or reader) from which it extracts the power required in the transponder. In the majority of RFID systems, which use UHF or microwaves, there is, apart from this unidirectional power transmission, also a data communication, which is typically bidirectional, based on a so-called challenge/response method. In this, the base station continually emits inquiry signals (data request, challenge), which will only be answered if there is an appropriate transponder in the effective range of this base station. In this case, a transponder which is within the immediate environment of the base station reacts with an reply signal (response). Only when a complete and valid command has been received does data communication take place between the transponder and the base station. The transponder can now be operated either synchronously or asynchronously with the base station. Such RFID transponders are used, for example, for identifying objects, such as goods, documents and the like.
Unlike conventional wire-based data communications, with this type of data communication the data communication between the base station and a corresponding transponder takes place virtually as a stand-alone activity, and to some extent in the background, with no need at all for a user to be present. I.e. the data communication is started up as soon as an authenticated transponder is within the effective range of the associated base station. Whereas, for example, when a data medium such as a diskette, a USB stick or the like, is being read from, it must be deliberately brought into contact with an appropriate reader, and in the case of wire-based data communication it must also be deliberately initiated by the user. This is not the case for RFID-based data communication.
This has some significant advantages, e.g. for identification in the field of logistics, in warehouses and the like. However, the technology of RFID-based data communications also has some serious disadvantages which must be taken into account for many applications.
One such problem relates to the unauthorized reading out of data contained in an RFID transponder, in particular when this data is security-critical data. For these reasons, an RFID-based data communication system typically also incorporates a security mechanism which, for example, safeguards the data communication by modulating onto the transmitted signal from the base station a security code, which can only be decoded and evaluated by the transponders authorized for the data communication. After successful evaluation, the transponder which is authorized, i.e. authenticated, for the data communication then transmits back to the base station a reply signal, which also contains a security code which can then in turn be evaluated by the base station. Thus, by these security codes a mutual authentication is effected both in the transponder and also in the base station, to avoid an unauthorized user (or hacker) connecting in to the data communication unnoticed, and thus being able to read out security-critical data.
An authentication of this type can be structured to be as demanding as required. However, an important external condition in the case of RFID-based data communication is that the data communication taking place between the base station and transponder should be as simple and as fast as possible. One reason for this is that the transponder typically only has modest resources, i.e. on the one hand low power resources and on the other hand small memory and computational resources, so that the authorization should typically evaluate and authenticate the smallest possible amounts of data. On the other hand, this authentication should also be carried out as quickly as possible because, especially in the case of dynamic RFID-based data communication systems, the transponder which is to be authenticated is very often within the effective range of the base station concerned for a short period of time. Within this short time it is necessary, on the one hand, to establish the data communication link, to authenticate this and then to effect the exchange of data.
With the mass application of RFID-based data communication systems which is to be expected in future, in particular in the commercial environment but also in the private, there is an increased need to make available simple but nonetheless effective measures against impermissible reading out of RFID-based data, to protect the security of a user's data. Here, the following three categories of protection, and hence of security against eavesdropping, are distinguished:
1. Protection of Private Data (Data Privacy):
Ensuring the protection of private data means that an unauthorized user must not be able to infer the identity of a transponder by eavesdropping on the data communication between it and the base station, or alternatively even by actively addressing the transponder. Otherwise this unauthorized user would obtain security-critical, sensitive items of data which are, for example, held in the transponder. Such sensitive items of data could for example contain user-specific information.
2. Protection of the Private Area (Location Privacy):
To ensure location privacy, it is necessary to prevent an unauthorized user being in a position, by eavesdropping on the data communication between the base station and the transponder, or even by some form of active addressing of the transponder at two different points in time, to obtain location-related data about the transponder. So it is necessary to ensure, in particular, that an unauthorized user cannot deduce from this that the transponder in each case is the same, or even possibly different, because otherwise he can deduce so-called movement profiles (tracking) of individual transponders, and hence also of their users. Here again, the information is security-critical and sensitive, and must be protected.
3. Guaranteeing Forward Security:
Finally, it must also be impossible for an unauthorized user to assign any data communication, which was for example recorded between a base station and a transponder some time in the past, to a particular transponder, even if that user should at a later point in time bring to light secret data for this particular transponder.
In order to be able to guarantee the protection just mentioned, or the corresponding security, the reply signals transmitted back from a transponder to a base station when several inquiries are made must appear to an unauthorized user as different and random, even if the base station sends the same inquiry signal several times to the same transponder. For this purpose there are a wide variety of approaches which are intended to guarantee the highest possible security. Some of them are outlined briefly below:
An approach to privacy protection for RFID tags is described in Engels et al., “Security and privacy aspects of low-cost radio frequency identification Systems”, International Conference on Security in Pervasive Computing, March 2003 (Engels et al.). With this solution, there is a unique identification code (ID) which is replaced by a random temporary identification number, the META-ID. A transponder replies solely to inquiries which contain the META-ID, whereby only an authorized base station which belongs to the system can deduce the actual identity of the transponder from it. This does indeed give data privacy protection, but not a protection against tracking or against eavesdropping at two different points in time, as applicable, so that here there is also the undesirable possibility of recognizing movement profiles.
Engels et al., “RFID Systems and security and privacy implications”, Cryptographic Hardware and Embedded Systems—CHES, August 2003 (Engels et al. 2) describes a method whereby an identification code (ID) is randomized for each transmission. The randomization is here effected with the help of a so-called hash function. However, implementing this hash function on a transponder calls for relatively large hardware capabilities, and thus computational effort. Apart from which, a disadvantage in this case is that the method offers no forward security.
Another method, using a hardware implementation based on AES, is described in Feldhofer et al., “Strong Authentication for RFID Systems Using the AES Algorithm”, Workshop on Cryptographic Hardware Embedded Systems—CHES, August 2004 (Feldhofer et al.). This method is a derivative of the so-called three-pass-mutual-authentication protocol in accordance with ISO Standard 9798. This protocol does offer protection against tracking, but no forward security.
Ohkubo et al. “Cryptographic Approach to Privacy-Friendly Tags”, RFID Privacy Workshop, November 2003 (Ohkubo et al.) describes a method based on a hash function. Here, a secret item of data S1 on a transponder is replaced by Si+1=Hash(S1) after each inquiry from a reader. This approach ensures forward security, because it is not possible from a knowledge of the current state Si to deduce earlier states Sk (where k>i). However, because of the hardware demands this poses and the associated costs, this method is not very suitable in practice for transponders.
For the purpose of securing data communications between a base station and a transponder, data communication is effected by an exchange of cryptographic data. Virtually all the methods known to date, such as for example the methods described above under Engels et al., Engels et al. 2, Feldhofer et al., Ohkubo et al., are based on symmetric cryptography. With such systems, each transponder contains a secret key which is stored in the base station, or to which the base station at least has a secure access, for example in that the secret key is stored in a central secure database.
Apart from the symmetric encryption methods, there also exist so-called asymmetric encryption methods. These asymmetric cryptography methods are based on a private and a public key. In this case, the public key is generated from a private key by a predetermined algorithm. The important feature of these cryptographic encryption methods is that the reverse, that is to say the determination of the private key from the public key, is scarcely feasible within a finite time with the computational capacities which are available.
It has been found to be advantageous to use cryptographic encryption algorithms based on elliptic curves, because these give high security with short key lengths. Such cryptographic encryption methods based on elliptical curves are very efficient, the particular reason for this being that, unlike known cryptographic methods, with these methods there are no known methods of attack with a less than exponential running time. Put another way, this means that the security gain per bit in the security parameter used is higher in the case of methods based on elliptical curves, and hence for practical applications significantly shorter key lengths can be used. Thus cryptographic methods based on elliptical curves perform better and require a smaller bandwidth for transmission of the system parameters than do other cryptographic methods for a comparable level of achievable security.
Hence, cryptographic methods represent a compromise between the level of security which can be expected and the computational effort for encrypting the data. In the German patent application DE 101 61 138 AI it is shown that it is possible to determine the scalar multiple of a point using only the X-coordinate of this point, even without referring to the Y-coordinate. This publication also describes corresponding computational rules for any arbitrary field. These permit significantly more efficient implementations of the point arithmetic, e.g. a Montgomery ladder, for the scalar multiplication, a smaller number of field multiplications per point addition and a smaller number of registers for the point representation of the intermediate results.